package main

import (
	"strconv"
	"strings"
)

// 394. 字符串解码
func main() {
	s := "3[a]2[bc]"
	//s = "100[leetcode]"
	s2 := decodeString(s)
	println(s2)
}

func decodeString(s string) string {
	var stack []string
	sLen := len(s)

	var ptr int

	for ptr < sLen {
		cur := s[ptr]
		if cur >= '0' && cur <= '9' { //如果是数字，解析数字入栈
			digital := getRepeatNum(&ptr, s)
			stack = append(stack, digital)
		} else if cur == ']' { // 开始出栈，找到[和数字重新入栈
			var tempStr string

			for stack[len(stack)-1] != "[" {
				var preStr string
				stack, preStr = stack[:len(stack)-1], stack[len(stack)-1]
				tempStr = tempStr + preStr
			}
			// 把[出栈，拿到数字
			var digitalNumStr string
			stack, digitalNumStr = stack[:len(stack)-2], stack[len(stack)-2]

			// 循环遍历 digitalNumStr 次，重新入栈
			repeatNum, _ := strconv.Atoi(digitalNumStr)
			for j := 0; j < repeatNum; j++ {
				for k := len(tempStr) - 1; k >= 0; k-- {
					stack = append(stack, string(tempStr[k]))
				}
			}
			ptr++
		} else { // 入栈
			stack = append(stack, string(cur))
			ptr++
		}
	}

	return strings.Join(stack, "")
}

func getRepeatNum(ptr *int, s string) string {
	digitalNum := ""
	for ; s[*ptr] >= '0' && s[*ptr] <= '9'; *ptr++ {
		digitalNum = digitalNum + string(s[*ptr])
	}
	return digitalNum
}

// 给定一个经过编码的字符串，返回它解码后的字符串。
//
//编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
//
//你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
//
//此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
//
//示例 1：
//
//输入：s = "3[a]2[bc]"
//输出："aaabcbc"
//示例 2：
//
//输入：s = "3[a2[c]]"
//输出："accaccacc"
//示例 3：
//
//输入：s = "2[abc]3[cd]ef"
//输出："abcabccdcdcdef"
//示例 4：
//
//输入：s = "abc3[cd]xyz"
//输出："abccdcdcdxyz"
//
//
//提示：
//
//1 <= s.length <= 30
//s 由小写英文字母、数字和方括号 '[]' 组成
//s 保证是一个 有效 的输入。
//s 中所有整数的取值范围为 [1, 300]
